package offer;

public class offer_0068_2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return low(root,p,q);
    }
    public TreeNode low(TreeNode node,TreeNode p,TreeNode q){
        if(node==null) return null;
        if(node.val==p.val||node.val==q.val){
            return node;
        }
        boolean left=search(node.left,p)||search(node.left,q);
        boolean right=search(node.right,p)||search(node.right,q);
        if(left&&right) return node;
        else if(left) return low(node.left,p,q);
        return low(node.right,p,q);
    }
    public boolean search(TreeNode node,TreeNode p){
        if(node==null) return false;
        if(node.val==p.val) return true;
        return search(node.left,p)||search(node.right,p);
    }
}
